#define _CRT_SECURE_NO_WARNINGS
#include<iostream>
using namespace std;
#include<string>
template<class K,class V>
struct BSTreeNode
{
	BSTreeNode<K,V>* left;
	BSTreeNode<K,V>* right;
	K _key;
	V _value;
	BSTreeNode(const K&key,const V&value)
		:left(nullptr),right(nullptr),_key(key),_value(value)
	{

	}
};
template<class K, class V>
class BSTree
{
	typedef BSTreeNode<K, V> Node;
public:
	BSTree()
		:_root(nullptr)
	{

	}
	bool Insert(const K& key, const V& value)
	{
		return _Insert(_root,key, value);
	}
	Node* Find(const K& key)
	{
		return _Find(_root, key);
	}
	bool Erase(const K& key)
	{
		return _Erase(_root, key);
	}
	
	void InOrder()
	{
		_InOrder(_root);
	}
private:
	bool _Insert(Node*&root, const K& key, const V& value)
	{
		if (root == NULL)
		{
			root = new Node(key, value);
			return true;
		}
			
		if (key > root->_key)
			{
				_Insert(root->right, key, value);
			}
		else if (key < root->_key)
			{
				_Insert(root->left, key, value);
			}
		else
		    {
			return false;
		     }
	}
	Node* _Find(Node*&root,const K& key)
	{
		if (root == NULL)
		{
			return NULL;
		}
		if (key > root->_key)
		{
			_Find(root->right, key);
		}
		else if (key < root->_key)
		{
			_Find(root->left, key);
		}
		else//找到了
		{
			return root;
		}
	}
	//没有孩子/只有一个孩子 直接删除
	//有两个孩子 替换法（找左子树最右节点/右子树最左节点）
	bool _Erase(Node*&root,const K& key)
	{
		// 1. 未找到要删除的节点
		if (root == nullptr)
			return false;

		// 2. 查找要删除的节点
		if (key < root->_key)
		{
			return _Erase(root->left, key);  // 去左子树找
		}
		else if (key > root->_key)
		{
			return _Erase(root->right, key); // 去右子树找
		}
		//找到了
		
		else
		{
			Node* del = root;
			if (root->left == NULL)
			{
				root = root->right;
			}
			else if (root->right == NULL)
			{
				root = root->left;
			}
			else//有两个孩子，找左子树最右节点
			{
				Node* leftMax = root->left;
				while (!leftMax->right)
				{
					leftMax = leftMax->right;
				}
				swap(leftMax->_key, root->_key);
				//return _Erase(leftMax, key);不能这么写，因为在右树找不到key。
                return _Erase(root->left,key);//因为是最右节点所以最多只有左孩子，没有右孩子
			}
			delete del;
			return true;
		}
		
	}
	void _InOrder(Node* root)
	{
		if (root == nullptr) return;
		_InOrder(root->left);
		cout << root->_key << ":" << root->_value<<endl;
		_InOrder(root->right);
	}
	Node* _root = nullptr;
};

void TestBSTree()
{
	/*BSTree<string, string> dict;
	dict.Insert("insert", "插入");
	dict.Insert("erase", "删除");
	dict.Insert("left", "左边");
	dict.Insert("string", "字符串");

	string str;
	while (cin >> str)
	{
		auto ret = dict.Find(str);
		if (ret)
		{
			cout << str << ":" << ret->_value << endl;
		}
		else
		{
			cout << "单词拼写错误" << endl;
		}
	}*/

	string strs[] = { "苹果", "西瓜", "苹果", "樱桃", "苹果", "樱桃", "苹果", "樱桃", "苹果" };
	// 统计水果出现的次
	BSTree<string, int> countTree;
	for (auto str : strs)
	{
		auto ret = countTree.Find(str);
		if (ret == NULL)
		{
			countTree.Insert(str, 1);
		}
		else
		{
			ret->_value++;
		}
	}
	countTree.InOrder();
}
void test1()
{
	BSTree<int, int> num;
	num.Insert(6, 1);
	num.Insert(2, 3);
	num.Insert(3, 6);
	num.Insert(7, 5);
	num.Insert(10, 20);
	num.Insert(5, 0);
	num.Erase(7);
	num.Erase(5);
	num.InOrder();
}
int main()
{
	test1();

	return 0;
}
